//寻找中心数组下标
class Solution {
public:
    int pivotIndex(vector<int>& nums) 
    {
        //f(i) [0,i-1]的前缀和
        //f(i)=f(i-1)+nums[i-1]
        //g(i) [i+1,n-1]的前缀和
        //g(i)=g(i+1)+nums[i+1]
        vector<int>f(nums.size(),0);
        vector<int>g(nums.size(),0);
        for(int i=1;i<nums.size();i++)
        {
            f[i]=f[i-1]+nums[i-1];
        }
        for(int j=nums.size()-2;j>=0;j--)
        {
            g[j]=g[j+1]+nums[j+1];
        }
        for(int i=0;i<nums.size();i++)
        {
            if(f[i]==g[i]) return i;
        }
        return -1;
    }
};

//除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        //f[i]表示 [0,i-1]内所有元素的积
        //g[i]表示 [i+1,n-1]内所有元素的积
        int n=nums.size();
        vector<int>res(n);
        vector<int>f(n,1);
        vector<int>g(n,1);
        for(int i=1;i<n;i++)
        {
            f[i]=f[i-1]*nums[i-1];
        }
        for(int j=n-2;j>=0;j--)
        {
            g[j]=g[j+1]*nums[j+1];
        }
        for(int i=0;i<n;i++)
        {
            res[i]=f[i]*g[i];
        }
        return res;
    }
};
